<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2130：魔塔</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">魔塔</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">魔塔</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                魔塔                </h1>
                <p>时间限制：100s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：259MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>魔塔是一款很流行的益智类小游戏。在游戏中，你可以控制主人公在魔塔中移动，走到怪兽面前便可以和怪兽来决斗，打败怪兽后可以得到金钱，并可以通过金钱来提高自己的攻击力、防御力、血量，从而变得更强大。然而，即便你拥有再高的攻击力、防御力，可以天下无敌，但一扇小小的门就可以阻止你无法前进。在游戏中，有红、黄、蓝三种颜色的门，并对应有红、黄、蓝三种颜色的钥匙。如果你想通过一扇门，需要消耗一把对应颜色的钥匙打开这扇门，如果你没有这种颜色的钥匙，便不能通过。现在你得到一款加强版的魔塔游戏：首先，门和钥匙的颜色不再是3种，而是n种，定为1~n号颜色。对于i号颜色的钥匙你有Ki把。并且之后你不会以任何形式得到任何颜色的钥匙。在你面前有三座n层的魔塔A、B、C。每座魔塔的入口处和相邻两层之间都会有一扇门。对于每座魔塔，恰好有n扇门，并且这n扇门的颜色恰好各不相同。其中，A魔塔中通往第i层的门颜色为DoorAi。（DoorBi、DoorCi的定义与DoorAi类似）在每座魔塔的每一层都有一定数量的怪兽，但这些怪兽根本打不过强大的你，你可以不费一滴血就秒杀这些怪兽，并得到杀死他们的金钱。我们已经为你统计好，消灭A魔塔第j层中所有的怪兽，可以得到的金钱数为GoldAi。（GoldBi、GoldCi的定义与GoldAi类似）现在，就请你来决策，如何运用这些钥匙，能得到最多的金钱，并告诉我们最多能获得多少金钱。</p></p><hr/><h3>输入格式</h3><p><p>第一行一个字符（A~F），表示数据类型（在下面数据规模中有详细介绍）第二行一个整数m，表示有几组测试数据。之后给出m组数据，对于每组数据有九行： 第一行一个整数n，表示魔塔层数。第二行一个数列Ki。第三行至第五行，每行一个数列，分别为DoorA、DoorB、DoorC。第六行至第八行，每行一个数列，分别为GoldA、GoldB、GoldC。第九行为一个空行。</p></p><hr/><h3>输出格式</h3><p><p>输出应包含m行，每行一个正整数，为最大能获得的金钱数。</p></p><hr/><h3>样例输入</h3><pre>A
2
5
1 2 1 1 2
1 2 3 4 5
2 4 3 5 1
5 4 3 2 1
1 1 1 1 5
1 2 2 3 3
1 2 1 1 1

5
1 2 1 1 2
1 2 3 4 5
2 4 3 5 1
5 4 3 2 1
1 1 1 1 50
1 2 2 3 3
1 2 1 1 1

</pre><hr/><h3>样例输出</h3><pre>12
56
【样例说明】
对于第一个数据：
1 2 3 4 5     第一个魔塔不用钥匙，能得到0金钱；
2 4 3 5 1)    第二个魔塔用1、2、3、4、5号钥匙，得到11金钱；
5)4 3 2 1     第三个魔塔用5号钥匙，得到1金钱；
最多可得到12金钱。
对于第二个数据：
1 2 3 4 5)    第一个魔塔用1、2、3、4、5号钥匙，能得到54金钱；
2)4 3 5 1     第二个魔塔用2号钥匙，得到1金钱；
5)4 3 2 1     第三个魔塔用5号钥匙，得到1金钱；
最多可得到56金钱。
【数据规模】
对于全部数据，满足：
1<=m<=10；
1<=n<=100000；
1<=Ki<=2；
0<= GoldAi、 GoldBi、 GoldCi <=2000；
DoorA、DoorB、DoorC为三个1到n的排列。
数据共分为六类：A、B、C、D、E、F，他们分别有各自的特征：
A类数据占10%，保证n<=100。
B类数据占10%，保证n<=1000。
C类数据占10%，保证GoldCi=0，即第三座塔中没有任何金钱。
D类数据占20%，保证Ki=1，即每种钥匙你都只有一把。
E类数据占30%，保证DoorA、DoorB、DoorC三个1到n的排列为随机产生的数列。
F类数据占20%，没有其他特征。
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2130" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2130" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>